package Hot100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-12-22 15:20
 */
public class combinationSum39 {
    /**39. 组合总和
     * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ，
     * 并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     * 回溯：
     * 路径：已选择过的数组元素
     * 选择列表：index位的元素选择或者不选择
     * 终止条件：target被减少到小于0，target==0则找到答案
     * */
    List<List<Integer>> res=new ArrayList<>();
    void backtrack(int[] candidates, int index, int target, LinkedList<Integer> path){
        if (target==0){
            res.add(new LinkedList<>(path));
            return;
        }
        if (target<0) return;
        if (index>=candidates.length) return;
        //做出选择,选择要当前元素，则下一步还可以选择当前元素，所有index不会+1
        path.add(candidates[index]);
        backtrack(candidates,index,target-candidates[index],path);
        path.removeLast();
        //若不要当前元素，则下一步也只能从index+1开始选择
        backtrack(candidates,index+1,target,path);
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates,0,target,new LinkedList<>());
        return res;
    }
}
